#include <stdio.h>
#include <stdlib.h>
#define maxsize 100

// 二叉树树的结构
typedef struct BNode{
    BNode *rchild;
    BNode *lchild;
    int data;
}BNode,*BTree;

//队列的结构
typedef struct Queue{
    int front;
    int rear;
    BNode * node[maxsize];
}Queue;

// 层序遍历
void layerOrder(BTree T){
    if(T == NULL)
        return;
    //初始化队列
    Queue q;
    q.front = q.rear = 0;

    //根节点入队
    q.node[q.rear] = T;
    q.rear = (q.rear + 1) % maxsize;

    while(q.rear != q.front){
        //队首结点出队并访问
        BNode *temp = q.node[q.front];
        q.front = (q.front + 1) % maxsize;
        printf("%d ",temp->data);

        //队首结点左右孩子入队
        if(temp->lchild != NULL){
            q.node[q.rear] = temp->lchild;
            q.rear = (q.rear + 1) % maxsize;
        }
        if(temp->rchild != NULL){
            q.node[q.rear] = temp->rchild;
            q.rear = (q.rear + 1) % maxsize;
        }
    }

}

// 求第k层的节点个数
int getNumBylayer(BTree T,int k){
    if(T == NULL)
        return 0;

    //初始化队列
    Queue q;
    q.front = q.rear = 0;

    //根节点入队
    q.node[q.rear] = T;
    q.rear = (q.rear + 1) % maxsize;
    int count = 1;
    while(q.rear != q.front){
        int num = (q.rear - q.front + maxsize) % maxsize;
        if(count == k){
            return num;
        }
        for(int i = 0;i<num;i++)
        {
            //队首结点出队并访问
            BNode *temp = q.node[q.front];
            q.front = (q.front + 1) % maxsize;

            //队首结点左右孩子入队
            if(temp->lchild != NULL){
                q.node[q.rear] = temp->lchild;
                q.rear = (q.rear + 1) % maxsize;
            }
            if(temp->rchild != NULL){
                q.node[q.rear] = temp->rchild;
                q.rear = (q.rear + 1) % maxsize;
            }
        }
        count++;
    }
    return 0;
}

// 求树的宽度
BNode * GetNode(int x) {
    BNode *node = (BNode *)malloc(sizeof(BNode));
    node->data = x;
    node->lchild = NULL;
    node->rchild = NULL;
    return node;
}

int main() {
    BTree T = GetNode(1);
    T->lchild = GetNode(2);
    T->rchild = GetNode(3);
    T->lchild->lchild = GetNode(4);
    T->rchild->rchild = GetNode(5);
    T->rchild->lchild = GetNode(6);
    layerOrder(T);
    int num = getNumBylayer(T, 3);
    printf("===>%d ", num);
    return 0;
}